package zuoshen_video;

import java.util.*;

import org.junit.Test;

public class MyStackAndQueue {
    class MyStack {
        private int[] stack;
        private int top;
        private int capacity;

        public MyStack(int capacity) {
            this.stack = new int[capacity];
            this.top = -1;
            this.capacity = capacity;
        }

        public boolean push(int val) {
            if (top < capacity) {
                this.stack[++top] = val;
                return true;
            } else return false;
        }

        public int pop() {
            if (top < 0) return -1;
            return stack[top--];
        }

        public int size() {
            return top + 1;
        }

        public int peek() {
            if (top < 0) return -1;
            return stack[top];
        }
    }

 

    //在插入时，有移动数组的行为，效率不高，完全可以优化
    //队头、队尾可以只是观感上的，在数组中两者完全可以解耦
    class MyQueue1 {
        private int capacity;
        private int[] queue;
        private int size;
        private int head;
        private int tail;

        public MyQueue1(int capacity) {
            this.capacity = capacity;
            this.queue = new int[capacity];
            this.size = 0;
            this.head = -1;
            this.tail = -1;
        }

        public boolean enqueue(int val) {
            if (size == capacity) throw new ArrayIndexOutOfBoundsException("Index out of up-limit");
            if (tail == capacity - 1) {
                int idx = head;
                for (int i = 0; i < tail - head + 1; i++) {
                    queue[i] = queue[idx++];
                }
                head = 0;
                tail = size - 1;
            }
            this.queue[++tail] = val;
            if (head < 0) head = 0;
            size++;
            return true;
        }

        public int dequeue() {
            if (head < 0) throw new ArrayIndexOutOfBoundsException("Index out of bottom-limit");
            int res = queue[head++];
            size--;
            return res;
        }

        public int peek() {
            if (head < 0) throw new ArrayIndexOutOfBoundsException("Index out of bottom-limit");
            return queue[head];
        }

        public int size() {
            return size;
        }

        public String toString() {
            StringBuilder sb = new StringBuilder("[");
            for (int i = head; i <= tail; i++) {
                sb.append(queue[i] + ", ");
            }
            sb.delete(sb.length() - 2, sb.length());
            sb.append("]");
            return sb.toString();
        }
    }
       /* 
    利用size作为任何时候的判断条件
    利用head和tail一直指向队头队尾
    */
    class MyQueue {
        private int capacity;
        private int[] queue;
        private int size;
        private int head;
        private int tail;

        public MyQueue(int capacity) {
            this.capacity = capacity;
            this.queue = new int[capacity];
            this.size = 0;
            this.head = -1;
            this.tail = -1;
        }

        public boolean enqueue(int val) {
            if (size == capacity) throw new ArrayIndexOutOfBoundsException("Index out of up-limit");
            if (head == -1 && tail == -1) {
                //空队列
                head = 0;
                tail = 0;
                queue[0] = val;
            } else {
                //tail即将越界，将其循环到开头
                tail = tail == capacity - 1 ? 0 : tail + 1;
                queue[tail] = val;
            }
            size++;
            return true;
        }

        public int dequeue() {
            if (size == 0) throw new ArrayIndexOutOfBoundsException("Index out of bottom-limit");
            int res = queue[head];
            size--;
            //依然循环到开头
            head = head == capacity - 1 ? 0 : head + 1;
            return res;
        }

        public int peek() {
            if (head < 0) throw new ArrayIndexOutOfBoundsException("Index out of bottom-limit");
            return queue[head];
        }

        public int size() {
            return size;
        }

        public String toString() {
            StringBuilder sb = new StringBuilder("[");
            if (head <= tail) {
                for (int i = head; i <= tail; i++) {
                    sb.append(queue[i] + ", ");
                }
                
            } else {
                //tail在head后，说明分成了两份
                for (int i = head; i < queue.length; i++) {
                    sb.append(queue[i] + ", ");
                }
                for (int i = 0; i <= tail; i++) {
                    sb.append(queue[i] + ", ");
                }
            }
            sb.delete(sb.length() - 2, sb.length());
            sb.append("]");
            return sb.toString();
        }

    }

    //存在问题：当有重复的数时，pop()操作可能出现问题
    //优化1：每当有相等值，也进最小栈
    //优化2：只有stack入栈，help也随之入栈，不过若是比peek()为大于，只会将help的栈顶元素在压一次，这样在出栈时无需判断，两者一起出栈。
    class MinStack1 {
        private Stack<Integer> stack;
        private Stack<Integer> help;

        public MinStack1() {
            stack = new Stack<>();
            help = new Stack<>();
        }

        public void push(int val) {
            stack.push(val);
            if (help.isEmpty() || val <= help.peek()) help.push(val);
        }

        public int pop() {
            if (stack.isEmpty()) return -1;
            int res = stack.pop();
            if (!help.isEmpty() && help.peek() == res) help.pop();
            return res;
        }

        public int peek() {
            if (stack.isEmpty()) return -1;
            return stack.peek();
        }

        public int min() {
            if (stack.isEmpty()) return -1;
            return help.peek();
        }
    }

    class MinStack {
        private Stack<Integer> stack;
        private Stack<Integer> help;

        public MinStack() {
            stack = new Stack<>();
            help = new Stack<>();
        }

        public void push(int val) {
            stack.push(val);
            if (help.isEmpty() || val <= help.peek()) help.push(val);
            else help.push(help.peek()); //栈顶再进栈
        }

        public int pop() {
            if (stack.isEmpty()) return -1;
            int res = stack.pop();
            help.pop(); //help无脑跟着出栈
            return res;
        }

        public int peek() {
            if (stack.isEmpty()) return -1;
            return stack.peek();
        }

        public int min() {
            if (stack.isEmpty()) return -1;
            return help.peek();
        }
    }

    @Test 
    public void test() {
        MyQueue queue = new MyQueue(10);
        int[] nums = {98, 66, 80, 74, 94, 64, 90, 30, 28, 50};
        for (int i = 0; i < nums.length; i++) {
            queue.enqueue(nums[i]);
        }
        System.out.println(queue);
        queue.dequeue();
        queue.enqueue(1);
        System.out.println(queue);
        queue.dequeue();
        queue.enqueue(2);
        System.out.println(queue);
        System.out.println(queue.peek());
        System.out.println(queue.dequeue());
        System.out.println(queue);
    }

    class UseTowThisToMakeThat {
        class UseTowQueueToMakeStack {
            private Queue<Integer> q1;
            private Queue<Integer> q2;

            //将其中一个作为非空 q1
            public UseTowQueueToMakeStack() {
                q1 = new LinkedList<>();
                q2 = new LinkedList<>();
            }

            public void push(int val) {
                q1.offer(val);
            }

            public int pop() {
                if (q1.isEmpty()) return -1;
                int last = -1;
                while (!q1.isEmpty()) {
                    last = q1.poll();
                    if (q1.isEmpty()) { //最后一个元素不给进栈
                        break;
                    }
                    q2.offer(last);
                }
                //交换q1与q2,使得q1指向非空
                Queue<Integer> t = q1;
                q1 = q2;
                q2 = t;
                return last;
            }

            public int peek() {
                if (q1.isEmpty()) return -1;
                int last = -1;
                while (!q1.isEmpty()) {
                    last = q1.poll();
                    q2.offer(last); //peek()最后一个元素可以进栈
                }
                //交换q1与q2,使得q1指向非空
                Queue<Integer> t = q1;
                q1 = q2;
                q2 = t;
                return last;
            }
         }

         //指定s1不为空
        class UseTowStackToMakeQueue {
            private Stack<Integer> s1;
            private Stack<Integer> s2;
            public UseTowStackToMakeQueue() {
                s1 = new Stack<>();
                s2 = new Stack<>();
            }

            public void enqueue(int val) {
                s1.push(val);
            }

            public int dequeue() {
                if (s1.isEmpty()) return -1;
                while (!s1.isEmpty()) {
                    s2.push(s1.pop());
                }
                //交换s1与s2,使得s1不为空
                Stack<Integer> t = s1;
                s1 = s2;
                s2 = t;
                return s1.pop();
            }
        }
    }
}
